package code.oldCode.feishuSpecializedTraining.back_trace;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 26029
 * @date 2025/3/17
 * @description
 */
public class MyBackTrace2 {
    // 39. 组合总和
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> lists = new ArrayList<>();
        getComSum(target, candidates, 0, new ArrayList<>(), lists);
        return lists;
    }

    public void getComSum(int target, int[] candidates, int pos, List<Integer> list, List<List<Integer>> lists) {
        if (target < 0)
            return;
        if (target == 0) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int i = pos; i < candidates.length; i++) {
            list.add(candidates[i]);
            getComSum(target - candidates[i], candidates, i, list, lists);
            list.remove(list.size() - 1);
        }
    }

    // 40. 组合总和 II
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> lists = new ArrayList<>();
        // 排序，原因是为了把一样的数字集合在一起，便于处理重复的情况
        Arrays.sort(candidates);
        getComSum2(target, candidates, 0, new ArrayList<>(), lists);
        return lists;
    }

    public void getComSum2(int target, int[] candidates, int pos, List<Integer> list, List<List<Integer>> lists) {
        if (target < 0)
            return;
        if (target == 0) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int i = pos; i < candidates.length; i++) {
            // 处理重复的情况，不要连着处理相同的数
            if (i != pos && candidates[i] == candidates[i - 1])
                continue;
            list.add(candidates[i]);
            getComSum2(target - candidates[i], candidates, i + 1, list, lists);
            list.remove(list.size() - 1);
        }
    }

    // 131. 分割回文串
    public List<List<String>> partition(String s) {
        List<List<String>> stringLists = new ArrayList<>();
        getPartition(0, s, new ArrayList<>(), stringLists);
        return stringLists;
    }

    public void getPartition(int pos, String s, List<String> stringList, List<List<String>> stringLists) {
        if (pos == s.length()) {
            stringLists.add(new ArrayList<>(stringList));
            return;
        }
        for (int i = pos; i < s.length(); i++) {
            if (isRound(s, pos, i)) {
                stringList.add(s.substring(pos, i + 1));
                getPartition(i + 1, s, stringList, stringLists);
                stringList.remove(stringList.size() - 1);
            }
        }
    }

    public boolean isRound(String s, int begin, int end) {
        while (begin < end) {
            if (s.charAt(begin) != s.charAt(end))
                return false;
            begin++;
            end--;
        }
        return true;
    }
}
